Digital signature schemes are well-known in the prior art. In a conventional signature scheme, each user Publishes a public key while keeping a secret key. The user's signature for a message m is a value o which can be efficiently computed with knowledge of the secret key and then verified by anyone using only the known public key. It is hard to forge the user's signature, however, without knowledge of the secret key. One such digital signature scheme is the so-called Rabin scheme wherein a user U publishes a composite number n.sub.U, a product of 2 primes, as his public key, and keeps n.sub.u 's prime factorization as his secret key. The signature of a message (an integer between 1 and n.sub.U and relatively prime with n.sub.U) is then computed. If m is a square modulo n.sub.U, then its signature is .sigma.=.sqroot.m mod n.sub.U. If m is not a square, its signature is a pair (r, s) where .sigma.=.sqroot.m.multidot.r mod n.sub.U and r is a few-bit random number, so that m.multidot.r is a square mod n.sub.U. In Rabin's scheme, as in all currently known digital signature schemes, signing is feasible, though not always efficient, when the length of the public and secret keys are large.
It is also known in the prior art that of the various kinds of attacks that can be mounted by a forger against a signature scheme, the most general is an adaptive chosen plaintext attack. In this type of attack, the forger uses the signer to obtain sample signatures of messages of the forger's choice. The forger's choices are made dependent on the public key and on signatures returned by the user in response to the forger's previous requests. The knowledge gained by the forger can then be used to forge a signature of a message not previously signed or, at worst, to determine the secret key itself. Rabin's scheme, described above, is totally unsecure against an adaptive chosen plaintext attack.
In many applications; e.g., using an so-called "smart.revreaction. or intelligent card to effect commercial transactions, it would be desirable and necessary to be able to generate a digital signature immediately after a message has been chosen. However, because all currently-available signature schemes only compute the signature after selection of the message, digital signing techniques are not presently useful for such real-time applications. One method to overcome this problem would be to use more efficient computational techniques, however, such techniques are prohibitively expensive. Alternatively, the signer must be willing to compute and store the signature of all possible messages before the signing of individual messages takes place. This approach is also impractical.
It would therefore be desirable to have a new approach to digital signing which overcomes these and other problems associated with prior art techniques.